package com.example.demo.huawei;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//异位词指相同字母重新组合排列产生的新字符串
//
//返回这些子串的起始位置
//示例 1:
//
//输入: s = "cbaebabacd", p = "abc"
//输出: [0,6]
//解释:
//起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
//起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
// 示例 2:
//
//输入: s = "abab", p = "ab"
//输出: [0,1,2]
//解释:
//起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
//起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
//起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
public class Main18 {

    // 时间超限制了
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) {
            return res;
        }
        int left = 0;
        int right = 0;
        while (left < s.length() && right < s.length()) {
            right = left + p.length();
            String s1 = s.substring(left, right);
            //            System.out.println(s1);
            // 判断是不是异位次
            char[] chars = s1.toCharArray();
            char[] charsP = p.toCharArray();
            Arrays.sort(charsP);
            Arrays.sort(chars);
            if (Arrays.equals(charsP, chars)) {
                res.add(left);
            }
            left++;
        }
        return res;
    }

    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) {
            return result;
        }

        Map<Character, Integer> pCount = new HashMap<>();
        Map<Character, Integer> sCount = new HashMap<>();

        // 统计 p 中每个字符的出现次数
        for (char ch : p.toCharArray()) {
            pCount.put(ch, pCount.getOrDefault(ch, 0) + 1);
        }

        int pLength = p.length();

        // 遍历 s 的每个字符，维护一个大小为 p.length() 的滑动窗口
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            sCount.put(ch, sCount.getOrDefault(ch, 0) + 1);

            // 当窗口大小超过 p.length() 时，移除最左边的字符
            if (i >= pLength) {
                char leftChar = s.charAt(i - pLength);
                if (sCount.get(leftChar) == 1) {
                    sCount.remove(leftChar);
                } else {
                    sCount.put(leftChar, sCount.get(leftChar) - 1);
                }
            }

            // 比较当前窗口的字符频率与 p 的字符频率是否相同
            if (pCount.equals(sCount)) {
                result.add(i - pLength + 1);
            }
        }

        return result;
    }

    public static void main(String[] args) {
//        System.out.println(new Main18().findAnagrams("abab", "ab"));
//        System.out.println(new Main18().findAnagrams("cbaebabacd", "abc"));

//        System.out.println(new Main18().findAnagrams2("abab", "ab"));
        System.out.println(new Main18().findAnagrams2("cbaebabacd", "abc"));
    }
}